import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName MyTest
 * @Description TODO
 * @Author Quentin_zyj
 * @Date 2021/11/4 14:54
 */
public class MyTest {
    // 矩阵连乘
    static void matrix(int n, int[] p, int[][] s, int[][] m) {
        for (int i = 1; i <= n; i++) {
            m[i][i] = 0;
        }
        // 有多少个矩阵相乘
        for (int r = 2; r <= n; r++) {
            for (int i = 1; i <= n - r + 1; i++) {
                int j = i + r - 1;
                m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
                s[i][j] = i;
                for (int k = i + 1; k < j; k++) {
                    int temp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if (temp < m[i][j]) {
                        m[i][j] = temp;
                        s[i][j] = k;
                    }
                }
            }
        }
    }

    // 长江游艇
    static void yacht(int n, int[][] f) {
        for (int r = 2; r <= n; r++) {
            for (int i = 1; r <= n - r + 1; i++) {
                int j = i + r - 1;
                for (int k = i + 1; k < j; k++) {
                    int temp = f[i][k] + f[k][j];
                    if (temp < f[i][j]) {
                        f[i][j] = temp;
                    }
                }
            }
        }
    }

    // 最长公共子序列
    static void lcs(int m, int n, char[] x, char[] y, int[][] s, int[][] b) {
        for (int i = 1; i <= n; i++) {
            s[0][i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            s[i][0] = 0;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (x[i] == y[j]) {
                    b[i][j] = 1;
                    s[i][j] = s[i - 1][j - 1] + 1;
                } else if (s[i - 1][j] >= s[i][j - 1]) {
                    b[i][j] = 2;
                    s[i][j] = s[i - 1][j];
                } else {
                    b[i][j] = 3;
                    s[i][j] = s[i][j - 1];
                }
            }
        }
    }

    public static List<Character> result = new ArrayList<>();

    static void LCS(int i, int j, char[] x, int[][] b) {
        if (i == 0 || j == 0) {
            return;
        } else if (b[i][j] == 1) {
            result.add(x[i]);
            LCS(i - 1, j - 1, x, b);
        } else if (b[i][j] == 2) {
            LCS(i - 1, j, x, b);
        } else {
            LCS(i, j - 1, x, b);
        }

    }

    // 序列关系计数
    static int sequence(int n) {
        int[] A = new int[n];
        A[0] = 1;
        for (int i = 1; i <= n - 1; i++) {
            A[i] = 0;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = i - 1; j >= 1; j--) {
                A[j] = (j + 1) * (A[j - 1] + A[j]);
            }
        }
        int result = 0;
        for (int i = 0; i <= n - 1; i++) {
            result += A[i];
        }
        return result;
    }

    // 最优三角形剖分
    static void minWeight(int n, int[][] w, int[][] s, int[][] m) {
        for (int i = 1; i <= n; i++) {
            m[i][i] = 0;
        }
        for (int r = 2; r <= n; r++) {
            for (int i = 1; i <= n - r + 1; i++) {
                int j = i + r - 1;
                m[i][j] = m[i][i] + m[i + 1][j] + w[i - 1][i] + w[i][j] + w[j][i];
                s[i][j] = i;
                for (int k = i + 1; k < j; k++) {
                    int temp = m[i][k] + m[k + 1][j] + w[i - 1][k] + w[k][j] + w[j][i - 1];
                    if (temp < m[i][j]) {
                        m[i][j] = temp;
                        s[i][j] = k;
                    }
                }
            }
        }
    }

    //
    public static void main(String[] args) {
        System.out.println(sequence(3));
    }
}

// 背包问题
class backpack {
    // 背包容量
    static int c;
    // 物品数量
    static int n;
    // 当前重量
    static int cw;
    // 最优价值
    static int bestp;
    // 当前价值
    static int cp;
    // 物品数量数组
    static int[] w;
    // 物品价值数组
    static int[] p;

    static void back(int i) {
        if (i > n) {
            bestp = cp;
            return;
        }
        if (cw + w[i] <= c) {
            cw += w[i];
            cp += p[i];
            back(i + 1);
            cw -= w[i];
            cp -= p[i];
        }
        if (bound(i + 1) > bestp) {
            back(i + 1);
        }
    }

    static int bound(int i) {
        int cleft = c - cw;
        int b = cp;
        while (i <= n && w[i] <= cleft) {
            b += p[i];
            cleft -= w[i];
            i++;
        }
        if (i <= n) {
            b += p[i] * cleft / w[i];
        }
        return b;
    }
}

// 装载问题
class load {
    // 重物数量
    static int n;
    // 重物重量数组
    static int[] w;
    // 当前载重
    static int cw;
    // 当前解
    static int[] x;
    // 轮船1
    static int c1;
    // 轮船2
    static int c2;
    // 最优载重
    static int bestw;
    // 最有解
    static int[] bestx;
    // 剩余集装箱重量
    static int r;

    static void back(int i) {
        if (i > n) {
            if (cw > bestw) {
                bestw = cw;
                for (int j = 1; j <= n; j++) {
                    bestx[j] = x[j];
                }
            }
        }
        r -= w[i];
        if (cw + w[i] <= c1) {
            cw += w[i];
            x[i] = 1;
            back(i + 1);
            cw -= w[i];
        }
        if (r + cw > bestw) {
            x[i] = 0;
            back(i + 1);
        }
        r += w[i];
    }



}

// n后问题
class queue {
    static int n;
    // 当前解
    static int[] x;
    // 可行解个数
    static int result = 0;

    static void back(int i) {
        if (i > n) {
            result++;
            return;
        }
        for (int j = 1; j <= n; j++) {
           x[j] = i;
           if (place(i)) {
               back(i + 1);
           }
        }
    }

    static boolean place(int i) {
        for (int j = 1; j <= i; j++) {
            if (Math.abs(i - j) == Math.abs(x[i] - x[j]) || x[i] == x[j]) {
                return false;
            }
        }
        return true;
    }
}

// 售货员
class salesman {
    static int n;
    static int[][] g;
    static int[] x;
    static int[] bestx;
    static int cc;
    static int bestc;
    static int noedge;

    static void back(int i) {
        if (i == n) {
            if (g[x[i-1]][x[i]] != noedge && g[x[i]][1] != noedge &&
                (cc + g[x[i-1]][x[i]] + g[x[i]][1] <= bestc || bestc == noedge)) {
                for (int j = 1; j <= n; j++) {
                    bestx[j] = x[i];
                }
                bestc = cc + g[x[i-1]][x[i]] + g[x[i]][1];
            }
        } else {
            for (int j = i; j <= n; j++) {
                if (g[x[i-1]][x[j]] != noedge && (cc + g[x[i-1]][x[j]] < bestc  || bestc == noedge)) {
                    swap(x, i, j);
                    cc += g[x[i-1]][x[j]];
                    bestc = cc + g[x[i-1]][x[j]];
                    back(i + 1);
                    cc -= g[x[i-1]][x[j]];
                    swap(x, i, j);
                }
            }
        }
    }

    static void swap(int[] a, int i, int j) {
        a[i] += a[j];
        a[j] = a[i] - a[j];
        a[i] = a[i] - a[j];
    }
}